package 剑指专题.其他;


/*
 * Author：江松
 * Date：2023/4/2 10:47
 *
数组中出现次数超过一半的数字：
1,排序后的中间点
2，哈希表
3，候选法
若数组中存在众数，那么众数一定大于数组的长度的一半。
思想就是：如果两个数不相等，就消去这两个数，
最坏情况下，每次消去一个众数和一个非众数，那么如果存在众数，最后留下的数肯定是众数。

不断的选择候选人，以cnt作为候选人的生命期，如果匹配就cnt++，反之cnt--，若为0就更换候选人
 */

public class Main5 {
    public int MoreThanHalfNum_Solution(int [] array) {
        int len=array.length;
        int candidate=-1,cnt=0;
        for(int i=0;i<len;++i){
            if(cnt==0){
                candidate=array[i];
                cnt++;
            }else{
                if(candidate!=array[i]){
                    cnt--;
                }else cnt++;
            }
        }
        return candidate;
    }
}
